package tree

// https://leetcode-cn.com/problems/delete-node-in-a-bst/
// 删除搜索二叉树中的节点
// 算法: 查找删除节点 + 删除 + 替换节点
// 重新分配节点：将左子树移动到右子节点的最左子树上（即左子树一定比右子树最小的节点还小），然后右子树上移
// 时间复杂度: O(log(n))
func DeleteNode(root *TreeNode, key int) *TreeNode {
	if nil == root {
		return nil
	}
	// 查询需要删除的节点的位置
	toDeleteNode, preNode := findToDeleteNode(root, key)
	if nil == toDeleteNode {
		return root
	}

	// 被删除的节点就是头节点
	if nil == preNode {
		// 左子树上移，原右子树移动到左子树的最右节点
		// log.Printf("to delete head")
		if nil != root.Left {
			leftNode := root.Left
			rightestNode := findRightestNode(leftNode)
			rightestNode.Right = root.Right
			root.Left, root.Right = nil, nil
			return leftNode
		} else {
			rightNode := root.Right
			root.Right = nil
			return rightNode
		}
	} else if nil != toDeleteNode.Right {
		// 找到右子节点的最左节点
		leftestNode := findLeftestNode(toDeleteNode.Right)
		leftestNode.Left = toDeleteNode.Left
		deleteNodeByActualNode(toDeleteNode, preNode, toDeleteNode.Right)
	} else if nil != toDeleteNode.Left {
		deleteNodeByActualNode(toDeleteNode, preNode, toDeleteNode.Left)
	} else {
		deleteNodeByActualNode(toDeleteNode, preNode, nil)
	}
	return root
}

// 注意：搜索树可按照二分的方式查找
func findToDeleteNode(root *TreeNode, key int) (toDeleteNode *TreeNode, preNode *TreeNode) {
	preNode = nil
	currentNode := root
	for currentNode != nil {
		if key == currentNode.Val {
			toDeleteNode = currentNode
			return 
		}
		if key > currentNode.Val {
			preNode = currentNode
			currentNode = currentNode.Right
		} else {
			preNode = currentNode
			currentNode = currentNode.Left
		}
	}
	
	return
}

// 要求: preNode != nil
func deleteNodeByActualNode(toDeleteNode, preNode, toReplaceNode *TreeNode) {
	if preNode.Left == toDeleteNode {
		preNode.Left = toReplaceNode
	} else {
		preNode.Right = toReplaceNode
	}
	toDeleteNode.Left, toDeleteNode.Right = nil, nil
}

// 要求: root != nil
func findLeftestNode(root *TreeNode) *TreeNode {
	for {
		if root.Left == nil {
			return root
		}
		root = root.Left
	}
}

// 要求: root != nil
func findRightestNode(root *TreeNode) *TreeNode {
	for {
		if root.Right == nil {
			return root
		}
		root = root.Right
	}
}